home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / vis.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  23.7 KB  |  1,015 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. int bitbytes;                                       // (num_visleafs+63)>>3
  5. int bitlongs;
  6. int c_chains;
  7. int c_leafsee, c_portalsee;
  8. int c_portalskip, c_leafskip;
  9. int c_portaltest, c_portalpass, c_portalcheck;
  10. int c_vistest, c_mighttest;
  11. int count_sep;
  12. int leafon;                                       // the next leaf to be given to a thread to process
  13. int originalvismapsize;
  14. int testvislevel = 2;
  15. int totalvis;
  16. unsigned char *uncompressed;                               // [bitbytes*num_visleafs]
  17. unsigned char portalsee[MAX_PORTALS];
  18.  
  19. void CheckStack(register struct visleaf * leaf, register threaddata_t * thread)
  20. {
  21.   pstack_t *p;
  22.  
  23.   for (p = thread->pstack_head.next; p; p = p->next)
  24.     if (p->leaf == leaf)
  25.       Error("CheckStack: leaf recursion");
  26. }
  27.  
  28. /*
  29.  * ==============
  30.  * ClipToSeperators
  31.  * 
  32.  * Source, pass, and target are an ordering of portals.
  33.  * 
  34.  * Generates seperating planes canidates by taking two points from source and one
  35.  * point from pass, and clips target by them.
  36.  * 
  37.  * If target is totally clipped away, that portal can not be seen through.
  38.  * 
  39.  * Normal clip keeps target on the same side as pass, which is correct if the
  40.  * order goes source, pass, target.  If the order goes pass, source, target then
  41.  * flipclip should be set.
  42.  * ==============
  43.  */
  44. struct winding *ClipToSeperators(register struct winding * source, register struct winding * pass, register struct winding * target, register bool flipclip)
  45. {
  46.   int i, j, k, l;
  47.   struct plane plane;
  48.   vec3_t v1, v2;
  49.   float d;
  50.   vec_t length;
  51.   int counts[3];
  52.   bool fliptest;
  53.  
  54. // check all combinations       
  55.   for (i = 0; i < source->numpoints; i++) {
  56.     l = (i + 1) % source->numpoints;
  57.     VectorSubtract(source->points[l], source->points[i], v1);
  58.  
  59.     // fing a vertex of pass that makes a plane that puts all of the
  60.     // vertexes of pass on the front side and all of the vertexes of
  61.     // source on the back side
  62.     for (j = 0; j < pass->numpoints; j++) {
  63.       VectorSubtract(pass->points[j], source->points[i], v2);
  64.  
  65.       plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
  66.       plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
  67.       plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
  68.  
  69.       // if points don't make a valid plane, skip it
  70.  
  71.       length = plane.normal[0] * plane.normal[0]
  72.     + plane.normal[1] * plane.normal[1]
  73.     + plane.normal[2] * plane.normal[2];
  74.  
  75.       if (length < ON_EPSILON)
  76.     continue;
  77.  
  78.       length = 1 / sqrt(length);
  79.  
  80.       plane.normal[0] *= length;
  81.       plane.normal[1] *= length;
  82.       plane.normal[2] *= length;
  83.  
  84.       plane.dist = DotProduct(pass->points[j], plane.normal);
  85.  
  86.       //
  87.       // find out which side of the generated seperating plane has the
  88.       // source portal
  89.       //
  90.       fliptest = FALSE;
  91.       for (k = 0; k < source->numpoints; k++) {
  92.     if (k == i || k == l)
  93.       continue;
  94.     d = DotProduct(source->points[k], plane.normal) - plane.dist;
  95.     if (d < -ON_EPSILON) {                               // source is on the negative side, so we want all
  96.       // pass and target on the positive side
  97.  
  98.       fliptest = FALSE;
  99.       break;
  100.     }
  101.     else if (d > ON_EPSILON) {                           // source is on the positive side, so we want all
  102.       // pass and target on the negative side
  103.  
  104.       fliptest = TRUE;
  105.       break;
  106.     }
  107.       }
  108.       if (k == source->numpoints)
  109.     continue;                                   // planar with source portal
  110.  
  111.       //
  112.       // flip the normal if the source portal is backwards
  113.       //
  114.       if (fliptest) {
  115.     VectorNegate(plane.normal);
  116.     plane.dist = -plane.dist;
  117.       }
  118.  
  119.       //
  120.       // if all of the pass portal points are now on the positive side,
  121.       // this is the seperating plane
  122.       //
  123.       counts[0] = counts[1] = counts[2] = 0;
  124.       for (k = 0; k < pass->numpoints; k++) {
  125.     if (k == j)
  126.       continue;
  127.     d = DotProduct(pass->points[k], plane.normal) - plane.dist;
  128.     if (d < -ON_EPSILON)
  129.       break;
  130.     else if (d > ON_EPSILON)
  131.       counts[0]++;
  132.     else
  133.       counts[2]++;
  134.       }
  135.       if (k != pass->numpoints)
  136.     continue;                                   // points on negative side, not a seperating plane
  137.  
  138.       if (!counts[0]) {
  139.     continue;                                   // planar with seperating plane
  140.  
  141.       }
  142.  
  143.       //
  144.       // flip the normal if we want the back side
  145.       //
  146.       if (flipclip) {
  147.     VectorNegate(plane.normal);
  148.     plane.dist = -plane.dist;
  149.       }
  150.  
  151.       //
  152.       // clip target by the seperating plane
  153.       //
  154.       target = ClipWinding(target, &plane, FALSE);
  155.       if (!target)
  156.     return NULL;                                   // target is not visible
  157.  
  158.     }
  159.   }
  160.  
  161.   return target;
  162. }
  163.  
  164. /*
  165.  * ==================
  166.  * RecursiveLeafFlow
  167.  * 
  168.  * Flood fill through the leafs
  169.  * If src_portal is NULL, this is the originating leaf
  170.  * ==================
  171.  */
  172. void RecursiveLeafFlow(register int leafnum, register threaddata_t * thread, register pstack_t * prevstack)
  173. {
  174.   pstack_t stack;
  175.   struct visportal *p;
  176.   struct plane backplane;
  177.   struct winding *source, *target;
  178.   struct visleaf *leaf;
  179.   int i, j;
  180.   long *test, *might, *vis;
  181.   bool more;
  182.  
  183.   c_chains++;
  184.  
  185.   leaf = leafs[leafnum];
  186.   CheckStack(leaf, thread);
  187.  
  188. // mark the leaf as visible
  189.   if (!(thread->leafvis[leafnum >> 3] & (1 << (leafnum & 7)))) {
  190.     thread->leafvis[leafnum >> 3] |= 1 << (leafnum & 7);
  191.     thread->base->numcansee++;
  192.   }
  193.  
  194.   prevstack->next = &stack;
  195.   stack.next = NULL;
  196.   stack.leaf = leaf;
  197.   stack.portal = NULL;
  198.   if(!(stack.mightsee = (unsigned char *)tmalloc(bitbytes)))
  199.     Error("RecursiveLeafFlow: failed to allocate bitbytes!\n");
  200.   might = (long *)stack.mightsee;
  201.   vis = (long *)thread->leafvis;
  202.  
  203. // check all portals for flowing into other leafs       
  204.   for (i = 0; i < leaf->numportals; i++) {
  205.     p = leaf->portals[i];
  206.  
  207.     if (!(prevstack->mightsee[p->leaf >> 3] & (1 << (p->leaf & 7)))) {
  208.       c_leafskip++;
  209.       continue;                                       // can't possibly see it
  210.  
  211.     }
  212.  
  213.     // if the portal can't see anything we haven't allready seen, skip it
  214.     if (p->status == stat_done) {
  215.       c_vistest++;
  216.       test = (long *)p->visbits;
  217.     }
  218.     else {
  219.       c_mighttest++;
  220.       test = (long *)p->mightsee;
  221.     }
  222.     more = FALSE;
  223.     for (j = 0; j < bitlongs; j++) {
  224.       might[j] = ((long *)prevstack->mightsee)[j] & test[j];
  225.       if (might[j] & ~vis[j])
  226.     more = TRUE;
  227.     }
  228.  
  229.     if (!more) {                                   // can't see anything new
  230.  
  231.       c_portalskip++;
  232.       continue;
  233.     }
  234.  
  235. // get plane of portal, point normal into the neighbor leaf
  236.     stack.portalplane = p->plane;
  237.     VectorNegateTo(p->plane.normal, backplane.normal);
  238.     backplane.dist = -p->plane.dist;
  239.  
  240.     if (VectorCompare(prevstack->portalplane.normal, backplane.normal))
  241.       continue;                                       // can't go out a coplanar face
  242.  
  243.     c_portalcheck++;
  244.  
  245.     stack.portal = p;
  246.     stack.next = NULL;
  247.  
  248.     target = ClipWinding(p->winding, &thread->pstack_head.portalplane, FALSE);
  249.     if (!target)
  250.       continue;
  251.  
  252.     if (!prevstack->pass) {                               // the second leaf can only be blocked if coplanar
  253.  
  254.       stack.source = prevstack->source;
  255.       stack.pass = target;
  256.       RecursiveLeafFlow(p->leaf, thread, &stack);
  257.       FreeWinding(target);
  258.       continue;
  259.     }
  260.  
  261.     target = ClipWinding(target, &prevstack->portalplane, FALSE);
  262.     if (!target)
  263.       continue;
  264.  
  265.     source = CopyWinding(prevstack->source);
  266.  
  267.     source = ClipWinding(source, &backplane, FALSE);
  268.     if (!source) {
  269.       FreeWinding(target);
  270.       continue;
  271.     }
  272.  
  273.     c_portaltest++;
  274.  
  275.     if (testvislevel > 0) {
  276.       target = ClipToSeperators(source, prevstack->pass, target, FALSE);
  277.       if (!target) {
  278.     FreeWinding(source);
  279.     continue;
  280.       }
  281.     }
  282.  
  283.     if (testvislevel > 1) {
  284.       target = ClipToSeperators(prevstack->pass, source, target, TRUE);
  285.       if (!target) {
  286.     FreeWinding(source);
  287.     continue;
  288.       }
  289.     }
  290.  
  291.     if (testvislevel > 2) {
  292.       source = ClipToSeperators(target, prevstack->pass, source, FALSE);
  293.       if (!source) {
  294.     FreeWinding(target);
  295.     continue;
  296.       }
  297.     }
  298.  
  299.     if (testvislevel > 3) {
  300.       source = ClipToSeperators(prevstack->pass, target, source, TRUE);
  301.       if (!source) {
  302.     FreeWinding(target);
  303.     continue;
  304.       }
  305.     }
  306.  
  307.     stack.source = source;
  308.     stack.pass = target;
  309.  
  310.     c_portalpass++;
  311.  
  312.     // flow through it for real
  313.     RecursiveLeafFlow(p->leaf, thread, &stack);
  314.  
  315.     FreeWinding(source);
  316.     FreeWinding(target);
  317.   }
  318.  
  319.   tfree(stack.mightsee);
  320. }
  321.  
  322. /*
  323.  * ===============
  324.  * PortalFlow
  325.  * 
  326.  * ===============
  327.  */
  328. void PortalFlow(register struct visportal * p)
  329. {
  330.   threaddata_t data;
  331.  
  332.   if (p->status != stat_working)
  333.     Error("PortalFlow: reflowed\n");
  334.   p->status = stat_working;
  335.  
  336.   if(!(p->visbits = (unsigned char *)kmalloc(bitbytes)))
  337.     Error("PortalFlow: failed to allocate bitbytes!\n");
  338.  
  339.   memset(&data, 0, sizeof(data));
  340.   data.leafvis = p->visbits;
  341.   data.base = p;
  342.  
  343.   data.pstack_head.portal = p;
  344.   data.pstack_head.source = p->winding;
  345.   data.pstack_head.portalplane = p->plane;
  346.   data.pstack_head.mightsee = p->mightsee;
  347.  
  348.   RecursiveLeafFlow(p->leaf, &data, &data.pstack_head);
  349.  
  350.   p->status = stat_done;
  351. }
  352.  
  353. /*
  354.  * ===============================================================================
  355.  * 
  356.  * This is a rough first-order aproximation that is used to trivially reject some
  357.  * of the final calculations.
  358.  * 
  359.  * ===============================================================================
  360.  */
  361.  
  362. void SimpleFlood(register struct visportal * srcportal, register int leafnum)
  363. {
  364.   int i;
  365.   struct visleaf *leaf;
  366.   struct visportal *p;
  367.  
  368.   if (srcportal->mightsee[leafnum >> 3] & (1 << (leafnum & 7)))
  369.     return;
  370.   srcportal->mightsee[leafnum >> 3] |= (1 << (leafnum & 7));
  371.   c_leafsee++;
  372.  
  373.   leaf = leafs[leafnum];
  374.  
  375.   for (i = 0; i < leaf->numportals; i++) {
  376.     p = leaf->portals[i];
  377.     if (!portalsee[p - portals])
  378.       continue;
  379.     SimpleFlood(srcportal, p->leaf);
  380.   }
  381. }
  382.  
  383. /*
  384.  * ==============
  385.  * BasePortalVis
  386.  * ==============
  387.  */
  388. void BasePortalVis(void)
  389. {
  390.   int i, j, k;
  391.   struct visportal *tp, *p;
  392.   float d;
  393.   struct winding *w;
  394.  
  395.   for (i = 0, p = portals; i < num_visportals * 2; i++, p++) {
  396.     if(!(p->mightsee = (unsigned char *)kmalloc(bitbytes)))
  397.       Error("BasePortalVis: failed to allocate bitbytes!\n");
  398.     c_portalsee = 0;
  399.     memset(portalsee, 0, num_visportals * 2);
  400.  
  401.     for (j = 0, tp = portals; j < num_visportals * 2; j++, tp++) {
  402.       if (j == i)
  403.     continue;
  404.       w = tp->winding;
  405.       for (k = 0; k < w->numpoints; k++) {
  406.     d = DotProduct(w->points[k], p->plane.normal)
  407.       - p->plane.dist;
  408.     if (d > ON_EPSILON)
  409.       break;
  410.       }
  411.       if (k == w->numpoints)
  412.     continue;                                   // no points on front
  413.  
  414.       w = p->winding;
  415.       for (k = 0; k < w->numpoints; k++) {
  416.     d = DotProduct(w->points[k], tp->plane.normal)
  417.       - tp->plane.dist;
  418.     if (d < -ON_EPSILON)
  419.       break;
  420.       }
  421.       if (k == w->numpoints)
  422.     continue;                                   // no points on front
  423.  
  424.       portalsee[j] = 1;
  425.       c_portalsee++;
  426.  
  427.     }
  428.  
  429.     c_leafsee = 0;
  430.     SimpleFlood(p, p->leaf);
  431.     p->nummightsee = c_leafsee;
  432. //              printf ("portal:%4i  c_leafsee:%4i \n", i, c_leafsee);
  433.  
  434.   }
  435. }
  436.  
  437. /*
  438.  * 
  439.  * Some textures (sky, water, slime, lava) are considered ambien sound emiters.
  440.  * Find an aproximate distance to the nearest emiter of each class for each leaf.
  441.  * 
  442.  */
  443.  
  444. /*
  445.  * ====================
  446.  * SurfaceBBox
  447.  * 
  448.  * ====================
  449.  */
  450. void SurfaceBBox(__memBase, register struct dface_t * s, register vec3_t mins, register vec3_t maxs)
  451. {
  452.   int i;
  453.   short int j;
  454.   int e;
  455.   int vi;
  456.   float *v;
  457.  
  458.   mins[0] = mins[1] = 999999;
  459.   maxs[0] = maxs[1] = -99999;
  460.  
  461.   for (i = 0; i < s->numedges; i++) {
  462.     e = bspMem->dsurfedges[s->firstedge + i];
  463.     if (e >= 0)
  464.       vi = bspMem->dedges[e].v[0];
  465.     else
  466.       vi = bspMem->dedges[-e].v[1];
  467.     v = bspMem->dvertexes[vi].point;
  468.  
  469.     for (j = 0; j < 3; j++) {
  470.       if (v[j] < mins[j])
  471.     mins[j] = v[j];
  472.       if (v[j] > maxs[j])
  473.     maxs[j] = v[j];
  474.     }
  475.   }
  476. }
  477.  
  478. /*
  479.  * ====================
  480.  * CalcAmbientSounds
  481.  * 
  482.  * ====================
  483.  */
  484. void CalcAmbientSounds(__memBase)
  485. {
  486.   int i, j, k;
  487.   short int l;
  488.   struct dleaf_t *leaf, *hit;
  489.   unsigned char *vis;
  490.   struct dface_t *surf;
  491.   vec3_t mins, maxs;
  492.   float d, maxd;
  493.   int ambient_type;
  494.   struct texinfo *info;
  495.   struct mipmap *miptex;
  496.   int ofs;
  497.   float dists[NUM_AMBIENTS];
  498.   float vol;
  499.  
  500.   for (i = 0; i < num_visleafs; i++) {
  501.     leaf = &bspMem->dleafs[i + 1];
  502.  
  503.     //
  504.     // clear ambients
  505.     //
  506.     for (j = 0; j < NUM_AMBIENTS; j++)
  507.       dists[j] = 1020;
  508.  
  509.     vis = &uncompressed[i * bitbytes];
  510.  
  511.     for (j = 0; j < num_visleafs; j++) {
  512.       if (!(vis[j >> 3] & (1 << (j & 7))))
  513.     continue;
  514.  
  515.       //
  516.       // check this leaf for sound textures
  517.       //      
  518.       hit = &bspMem->dleafs[j + 1];
  519.  
  520.       for (k = 0; k < hit->nummarksurfaces; k++) {
  521.     surf = &bspMem->dfaces[bspMem->dmarksurfaces[hit->firstmarksurface + k]];
  522.     info = &bspMem->texinfo[surf->texinfo];
  523.     ofs = ((struct dmiptexlump_t *) bspMem->dtexdata)->dataofs[info->miptex];
  524.     miptex = (struct mipmap *) (&bspMem->dtexdata[ofs]);
  525.  
  526.     if (!strncasecmp(miptex->name, "sky", 3))
  527.       ambient_type = AMBIENT_SKY;
  528.     else if (!strncasecmp(miptex->name, "*slime", 6))
  529.       ambient_type = AMBIENT_SLIME;            // AMBIENT_SLIME;
  530.     else if (!strncasecmp(miptex->name, "*lava", 6))
  531.       ambient_type = AMBIENT_LAVA;
  532.     else if (miptex->name[0] == '*')
  533.       ambient_type = AMBIENT_WATER;
  534.     else
  535.       continue;
  536.  
  537.     // find distance from source leaf to polygon
  538.     SurfaceBBox(bspMem, surf, mins, maxs);
  539.     maxd = 0;
  540.     for (l = 0; l < 3; l++) {
  541.       if (mins[l] > leaf->maxs[l])
  542.         d = mins[l] - leaf->maxs[l];
  543.       else if (maxs[l] < leaf->mins[l])
  544.         d = leaf->mins[l] - mins[l];
  545.       else
  546.         d = 0;
  547.       if (d > maxd)
  548.         maxd = d;
  549.     }
  550.  
  551.     maxd = 0.25;
  552.     if (maxd < dists[ambient_type])
  553.       dists[ambient_type] = maxd;
  554.       }
  555.     }
  556.  
  557.     for (j = 0; j < NUM_AMBIENTS; j++) {
  558.       if (dists[j] < 100)
  559.     vol = 1.0;
  560.       else {
  561.     vol = 1.0 - dists[2] * 0.002;
  562.     if (vol < 0)
  563.       vol = 0;
  564.       }
  565.       leaf->ambient_level[j] = vol * 255;
  566.     }
  567.     mprogress(num_visleafs, i + 1);
  568.   }
  569. }
  570.  
  571. //=============================================================================
  572.  
  573. /*
  574.  * =============
  575.  * GetNextPortal
  576.  * 
  577.  * Returns the next portal for a thread to work on
  578.  * Returns the portals from the least complex, so the later ones can reuse
  579.  * the earlier information.
  580.  * =============
  581.  */
  582. struct visportal *GetNextPortal(void)
  583. {
  584.   int j;
  585.   struct visportal *p, *tp;
  586.   int min;
  587.  
  588.   min = 99999;
  589.   p = NULL;
  590.  
  591.   for (j = 0, tp = portals; j < num_visportals * 2; j++, tp++) {
  592.     if (tp->nummightsee < min && tp->status == stat_none) {
  593.       min = tp->nummightsee;
  594.       p = tp;
  595.     }
  596.   }
  597.  
  598.   if (p)
  599.     p->status = stat_working;
  600.  
  601.   return p;
  602. }
  603.  
  604. /*
  605.  * ===============
  606.  * CompressRow
  607.  * 
  608.  * ===============
  609.  */
  610. int CompressRow(register unsigned char * vis, register unsigned char * dest)
  611. {
  612.   int j;
  613.   int rep;
  614.   int visrow;
  615.   unsigned char *dest_p;
  616.  
  617.   dest_p = dest;
  618.   visrow = (num_visleafs + 7) >> 3;
  619.  
  620.   for (j = 0; j < visrow; j++) {
  621.     *dest_p++ = vis[j];
  622.     if (vis[j])
  623.       continue;
  624.  
  625.     rep = 1;
  626.     for (j++; j < visrow; j++)
  627.       if (vis[j] || rep == 255)
  628.     break;
  629.       else
  630.     rep++;
  631.     *dest_p++ = rep;
  632.     j--;
  633.   }
  634.  
  635.   return dest_p - dest;
  636. }
  637.  
  638. /*
  639.  * =============
  640.  * SortPortals
  641.  * 
  642.  * Sorts the portals from the least complex, so the later ones can reuse
  643.  * the earlier information.
  644.  * =============
  645.  */
  646. int PComp(register struct visportal *a, register struct visportal *b)
  647. {
  648.   if (a->nummightsee == b->nummightsee)
  649.     return 0;
  650.   if (a->nummightsee < b->nummightsee)
  651.     return -1;
  652.   return 1;
  653. }
  654.  
  655. void SortPortals(void)
  656. {
  657.   heapsort(portals, num_visportals * 2, sizeof(struct visportal), PComp);
  658. }
  659.  
  660. /*
  661.  * ===============
  662.  * LeafFlow
  663.  * 
  664.  * Builds the entire visibility list for a leaf
  665.  * ===============
  666.  */
  667. void LeafFlow(__memBase, register int leafnum)
  668. {
  669.   struct visleaf *leaf;
  670.   unsigned char *outbuffer;
  671.   unsigned char compressed[MAX_MAP_LEAFS / 8];
  672.   int i, j;
  673.   int numvis;
  674.   struct visportal *p;
  675.  
  676. //
  677.   // flow through all portals, collecting visible bits
  678.   //
  679.   outbuffer = uncompressed + leafnum * bitbytes;
  680.   leaf = leafs[leafnum];
  681.   for (i = 0; i < leaf->numportals; i++) {
  682.     p = leaf->portals[i];
  683.     if (p->status != stat_done)
  684.       Error("portal not done\n");
  685.     for (j = 0; j < bitbytes; j++)
  686.       outbuffer[j] |= p->visbits[j];
  687.   }
  688.  
  689.   if (outbuffer[leafnum >> 3] & (1 << (leafnum & 7)))
  690.     Error("Leaf portals saw into leaf\n");
  691.  
  692.   outbuffer[leafnum >> 3] |= (1 << (leafnum & 7));
  693.  
  694.   numvis = 0;
  695.   for (i = 0; i < num_visleafs; i++)
  696.     if (outbuffer[i >> 3] & (1 << (i & 3)))
  697.       numvis++;
  698.  
  699. //
  700.   // compress the bit string
  701.   //
  702.   if (bspMem->visOptions & VIS_VERBOSE)
  703.     mprintf("----- leaf %4i ---------\n%5i visible\n", leafnum, numvis);
  704.   totalvis += numvis;
  705.  
  706.   i = CompressRow(outbuffer, compressed);
  707.  
  708.   if ((bspMem->visdatasize + i) > bspMem->max_visdatasize)
  709.     ExpandClusters(bspMem, LUMP_VISIBILITY);
  710.   memcpy(bspMem->dvisdata + bspMem->visdatasize, compressed, i);
  711.   bspMem->dleafs[leafnum + 1].visofs = bspMem->visdatasize;                   // leaf 0 is a common solid
  712.   bspMem->visdatasize += i;
  713. }
  714.  
  715. /*
  716.  * ==================
  717.  * CalcPortalVis
  718.  * ==================
  719.  */
  720. void CalcPortalVis(__memBase)
  721. {
  722.   int i;
  723.   struct visportal *p;
  724.  
  725. // fastvis just uses mightsee for a very loose bound
  726.   if (bspMem->visOptions & VIS_FAST) {
  727.     for (i = 0; i < num_visportals * 2; i++) {
  728.       portals[i].visbits = portals[i].mightsee;
  729.       portals[i].status = stat_done;
  730.     }
  731.     return;
  732.   }
  733.  
  734.   leafon = 0;
  735.  
  736.   while((p = GetNextPortal())) {
  737.     PortalFlow(p);
  738.     if (bspMem->visOptions & VIS_VERBOSE)
  739.       mprintf("----- portal %4i -------\n %5i mightsee\n%5i cansee\n", (int)(p - portals), p->nummightsee, p->numcansee);
  740.   }
  741.   
  742.   if (bspMem->visOptions & VIS_VERBOSE) {
  743.     mprintf("%5i portalcheck\n%5i portaltest\n%5i portalpass\n", c_portalcheck, c_portaltest, c_portalpass);
  744.     mprintf("%5i c_vistest\n%5i c_mighttest\n", c_vistest, c_mighttest);
  745.   }
  746.  
  747. }
  748.  
  749. /*
  750.  * ==================
  751.  * CalcVis
  752.  * ==================
  753.  */
  754. void CalcVis(__memBase)
  755. {
  756.   int i;
  757.  
  758.   BasePortalVis();
  759.   //SortPortals();
  760.   CalcPortalVis(bspMem);
  761.  
  762. //
  763.   // assemble the leaf vis lists by oring and compressing the portal lists
  764.   //
  765.   for (i = 0; i < num_visleafs; i++) {
  766.     LeafFlow(bspMem, i);
  767.     mprogress(num_visleafs, i + 1);
  768.   }
  769.  
  770.   mprintf("%5i average leafs visible\n", totalvis / num_visleafs);
  771. }
  772.  
  773. /*
  774.  * ==============================================================================
  775.  * 
  776.  * PASSAGE CALCULATION (not used yet...)
  777.  * 
  778.  * ==============================================================================
  779.  */
  780.  
  781. bool PlaneCompare(register struct plane * p1, register struct plane * p2)
  782. {
  783.   int i;
  784.  
  785.   if (fabs(p1->dist - p2->dist) > 0.01)
  786.     return FALSE;
  787.  
  788.   for (i = 0; i < 3; i++)
  789.     if (fabs(p1->normal[i] - p2->normal[i]) > 0.001)
  790.       return FALSE;
  791.  
  792.   return TRUE;
  793. }
  794.  
  795. struct seperatingplane *Findpassages(register struct winding * source, register struct winding * pass)
  796. {
  797.   int i, j, k, l;
  798.   struct plane plane;
  799.   vec3_t v1, v2;
  800.   float d;
  801.   double length;
  802.   int counts[3];
  803.   bool fliptest;
  804.   struct seperatingplane *sep, *list;
  805.  
  806.   list = NULL;
  807.  
  808. // check all combinations       
  809.   for (i = 0; i < source->numpoints; i++) {
  810.     l = (i + 1) % source->numpoints;
  811.     VectorSubtract(source->points[l], source->points[i], v1);
  812.  
  813.     // fing a vertex of pass that makes a plane that puts all of the
  814.     // vertexes of pass on the front side and all of the vertexes of
  815.     // source on the back side
  816.     for (j = 0; j < pass->numpoints; j++) {
  817.       VectorSubtract(pass->points[j], source->points[i], v2);
  818.  
  819.       plane.normal[0] = v1[1] * v2[2] - v1[2] * v2[1];
  820.       plane.normal[1] = v1[2] * v2[0] - v1[0] * v2[2];
  821.       plane.normal[2] = v1[0] * v2[1] - v1[1] * v2[0];
  822.  
  823.       // if points don't make a valid plane, skip it
  824.  
  825.       length = plane.normal[0] * plane.normal[0]
  826.     + plane.normal[1] * plane.normal[1]
  827.     + plane.normal[2] * plane.normal[2];
  828.  
  829.       if (length < ON_EPSILON)
  830.     continue;
  831.  
  832.       length = 1 / sqrt(length);
  833.  
  834.       plane.normal[0] *= length;
  835.       plane.normal[1] *= length;
  836.       plane.normal[2] *= length;
  837.  
  838.       plane.dist = DotProduct(pass->points[j], plane.normal);
  839.  
  840.       //
  841.       // find out which side of the generated seperating plane has the
  842.       // source portal
  843.       //
  844.       fliptest = FALSE;
  845.       for (k = 0; k < source->numpoints; k++) {
  846.     if (k == i || k == l)
  847.       continue;
  848.     d = DotProduct(source->points[k], plane.normal) - plane.dist;
  849.     if (d < -ON_EPSILON) {                               // source is on the negative side, so we want all
  850.       // pass and target on the positive side
  851.  
  852.       fliptest = FALSE;
  853.       break;
  854.     }
  855.     else if (d > ON_EPSILON) {                           // source is on the positive side, so we want all
  856.       // pass and target on the negative side
  857.  
  858.       fliptest = TRUE;
  859.       break;
  860.     }
  861.       }
  862.       if (k == source->numpoints)
  863.     continue;                                   // planar with source portal
  864.  
  865.       //
  866.       // flip the normal if the source portal is backwards
  867.       //
  868.       if (fliptest) {
  869.     VectorNegate(plane.normal);
  870.     plane.dist = -plane.dist;
  871.       }
  872.  
  873.       //
  874.       // if all of the pass portal points are now on the positive side,
  875.       // this is the seperating plane
  876.       //
  877.       counts[0] = counts[1] = counts[2] = 0;
  878.       for (k = 0; k < pass->numpoints; k++) {
  879.     if (k == j)
  880.       continue;
  881.     d = DotProduct(pass->points[k], plane.normal) - plane.dist;
  882.     if (d < -ON_EPSILON)
  883.       break;
  884.     else if (d > ON_EPSILON)
  885.       counts[0]++;
  886.     else
  887.       counts[2]++;
  888.       }
  889.       if (k != pass->numpoints)
  890.     continue;                                   // points on negative side, not a seperating plane
  891.  
  892.       if (!counts[0])
  893.     continue;                                   // planar with pass portal
  894.  
  895.       //
  896.       // save this out
  897.       //
  898.       count_sep++;
  899.  
  900.       if(!(sep = (struct seperatingplane *)kmalloc(sizeof(struct seperatingplane))))
  901.         Error("FindPassages: failed to allocate seperating plane!\n");
  902.       sep->next = list;
  903.       list = sep;
  904.       sep->plane = plane;
  905.     }
  906.   }
  907.  
  908.   return list;
  909. }
  910.  
  911. /*
  912.  * ============
  913.  * CalcPassages
  914.  * ============
  915.  */
  916. void CalcPassages(void)
  917. {
  918.   int i, j, k;
  919.   int count, count2;
  920.   struct visleaf *l;
  921.   struct visportal *p1, *p2;
  922.   struct seperatingplane *sep;
  923.   struct passage *passages;
  924.  
  925.   mprintf("    - building passages...\n");
  926.  
  927.   count = count2 = 0;
  928.   for (i = 0; i < num_visleafs; i++) {
  929.     l = leafs[i];
  930.  
  931.     for (j = 0; j < l->numportals; j++) {
  932.       p1 = l->portals[j];
  933.       for (k = 0; k < l->numportals; k++) {
  934.     if (k == j)
  935.       continue;
  936.  
  937.     count++;
  938.     p2 = l->portals[k];
  939.  
  940.     // definately can't see into a coplanar portal
  941.     if (PlaneCompare(&p1->plane, &p2->plane))
  942.       continue;
  943.  
  944.     count2++;
  945.  
  946.     sep = Findpassages(p1->winding, p2->winding);
  947.     if (!sep) {
  948. //                                      Error ("No seperating planes found in portal pair");
  949.       count_sep++;
  950.       if(!(sep = (struct seperatingplane *)kmalloc(sizeof(struct seperatingplane))))
  951.             Error("CalcPassages: failed to allocate seperate plane!\n");
  952.       sep->next = NULL;
  953.       sep->plane = p1->plane;
  954.     }
  955.     if(!(passages = (struct passage *)kmalloc(sizeof(struct passage))))
  956.           Error("CalcPassages: failed to allocate passage!\n");
  957.     passages->planes = sep;
  958.     passages->from = p1->leaf;
  959.     passages->to = p2->leaf;
  960.     passages->next = l->passages;
  961.     l->passages = passages;
  962.       }
  963.     }
  964.   }
  965.  
  966.   mprintf("%5i numpassages (%i)\n", count2, count);
  967.   mprintf("%5i total passages\n", count_sep);
  968. }
  969.  
  970. //=============================================================================
  971.  
  972. bool vis(__memBase, int level, char *prtBuf)
  973. {
  974.   int i;
  975.  
  976.   mprintf("----- Vis ---------------\n");
  977.  
  978.   AllocClusters(bspMem, LUMP_VISIBILITY);
  979.   
  980.   if(!(bspMem->visOptions & VIS_MEM))
  981.     LoadPortals(prtBuf);
  982.   if(level)
  983.     testvislevel = level;
  984.  
  985.   originalvismapsize = num_visportals * ((num_visportals + 7) / 8);
  986.   bitbytes = ((num_visportals + 63) & ~63) >> 3;
  987.   bitlongs = bitbytes / sizeof(long);
  988.  
  989.   if(!(uncompressed = (char *)kmalloc(bitbytes * num_visleafs)))
  990.     Error("Vis: failed to allocate bitbytes!\n");
  991.  
  992.   mprintf("----- CalcVis -----------\n");
  993. //CalcPassages ();
  994.   CalcVis(bspMem);
  995.  
  996.   mprintf("%5i c_chains\n", c_chains);
  997.   mprintf("%5i visdatasize (compressed from %i)\n", bspMem->visdatasize, originalvismapsize);
  998.  
  999.   mprintf("----- CalcAmbientSounds -\n");
  1000.   CalcAmbientSounds(bspMem);
  1001.  
  1002.   for(i = 0; i < num_visleafs; i++)
  1003.     if(leafs[i])
  1004.       FreeLeaf(leafs[i]);
  1005.   for(i = 0; i < (num_visportals * 2); i++)
  1006.     if(portals[i].winding);
  1007.       FreeWinding(portals[i].winding);
  1008.   tfree(leafs);
  1009.   tfree(portals);
  1010.   kfree();
  1011.  
  1012.   return TRUE;
  1013. }
  1014.  
  1015.